//连通度
//connectivity.cpp

//求有向图和无向图的点或边连通度

//1)基础概念
//连通图G的连通度k是在该图中任意删去k-1个节点后，该图仍然是连通的
//但存在一个方案，使得删去k个节点后该图不连通，则称该图是k连通图，k为连通度
//这个概念早在本章第2节Tarjan算法的双连通分支中就有涉及到
//但求一个有向图或无向图的连通度需要通过最大流最小割模型转为用最大流算法求解
//
//在了解有向图和无向图的点或边连通度的解法之前，先回忆关于连通的几个概念
//割点，割边，点割集，边割集，点连通度，边连通度
//对于无向连通图G=<V,E>
//割点：
//连通分支中删去该节点后不再连通的节点
//割边：
//连通分支中删去该边后不再连通的边
//点割集：
//点集V中有这样的非空真子集V1，G中删去V1后不再连通
//但对于V1的任意真子集V2，G中删去V2后都仍然连通，称这样的点集V1是G的一个点割集
//边割集：
//边集E中有这样的非空真子集E1，G中删去E1后不再连通
//但对于E1的任意真子集E2，G中删去E2后都仍然连通，称这样的边集E1是G的一个边割集
//平凡图：
//只有一个节点，没有边的图
//非平凡图：
//有至少两个节点，一条边的图
//点割集和边割集性质：
//任何非平凡的无向连通图一定具有边割集
//而非平凡的无向连通图存在点割集的充要条件是该图中至少存在两个不相邻的相异节点
//点连通度：
//非平凡的无向连通图G的所有点割集V1的节点数量最少的点割集数量k即为图G的点连通度k
//即该图中删除任意k-1个节点后都仍然连通，但存在一个方案(点割集)使删除k个节点后不连通
//特别的当k = 2时，即该图任意删除1个节点都仍然连通
//但存在一个方案使删除2个节点后不再连通，称点连通度k = 2的连通分支(图)为点双连通分支
//边连通度：
//非平凡的无向连通图G的所有边割集E1的边数量最少的边割集数量k即为图G的边连通度k
//即该图中删去任意k-1条边后都仍然连通，但存在一个方案(边割集)使删除k条边后不再连通
//特别的当k = 2时，即该图任意删除1条边都仍然连通
//但存在一个方案使删除2条边后不再连通，称边连通度k = 2的连通分支(图)为边双连通分支
//
//2)构造流网络
//i)无向图的边连通度：
//对于无向图G，将每条边e(i, j)构造为两条边e(i, j)和e(j, i)
//即从节点i指向节点j和从节点j指向节点i的两条边，容量都为1
//即可得到对应的流网络图
//ii)有向图的边连通度：
//对于有向图G，将每条边e(i, j)设置为容量为1的边，其他都不需要修改
//即可得到对应的流网络图
//iii)无向图的点连通度：
//对于无向图G，将每个节点i拆分成i1和i2两个节点，并添加一条i1到i2容量为1的边e(i1, i2)
//对于原图G中的边e(i, j)，对应在新流网络中有边e(i2, j1)和e(j2, i1)且容量都为正无穷
//即可得到对应的流网络图
//iv)有向图的点连通度：
//对于有向图G，将每个节点i拆分成i1和i2两个节点，并添加一条i1到i2容量为1的边e(i1, i2)
//对于原图G中的边e(i, j)，对应在新流网络中有边e(i2, j1)，容量为正无穷(比无向图少一条)
//即可得到对应的流网络图
//实际上原图上节点i，j和从i到j的边e(i, j)在对应流网络中为节点i1，i2，j1和j2
//以及边e(i1, i2)(容量1)，e(i2, j1)(容量正无穷)，e(j1, j2)(容量1)，也是一条路径
//
//3)在构造的流网络上求最大流
//i)无向图和有向图的边连通度：
//在对应的流网络上任意选取一个节点i作为源点beg
//枚举其他所有与节点i不相邻的节点作为汇点，求所有汇点情况下的最大流
//其中最小的那个最大流即为原图图的边连通度
//在连通的无向图和有向图中，从任意一个节点出发可以到达其他所有任意的节点
//因此只需要随意选取一个节点作为源点，枚举其他所有不相邻节点作为汇点即可得到所有情况
//最小的最大流中，所有流量为1的边组成的边集即为最小的边割集
//ii)无向图和有向图的点连通度：
//点连通度的图构造方法其实是将点连通度的求解转化为了边连通度
//而求点连通度对应的流网络的最大流的方式，与边连通度的流网络相同
//也是在对应的流网络上任意选取一个节点i作为源点beg，枚举所有其他不相邻的节点求最大流
//其中最小的那个最大流即为原图的点连通度
//最小的最大流中，所有流量为1的边e(i1, i2)
//对应的原图中的同一节点i组成的点集即为最小的点割集

//void connectivity(graph_list g)
